package com.code.test.second.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.md
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1：
 * <p>
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为： [ [7], [2,2,3] ]
 * 示例 2：
 * <p>
 * 输入：candidates = [2,3,5], target = 8,
 * 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
 */
public class SCode39 {


    /**
     * 数字可以无限次被选取，所以不能用窗口、双指针
     */
    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 7};
        List<List<Integer>> ret = combine(nums, 7);
        System.out.println(ret.size());
        System.out.println(ret);
    }

    /**
     * 无重复元素
     * target = [任意数量组合]
     * 不能包含重复组合
     * 1<=candidates[i]<=200
     */

    /**
     * 解题：
     * 递归层次未知，因为可以任意组合
     * <p>
     * List<List<Integer>> ret 最终结果
     * List<Integer> 单个组合
     */

    static List<List<Integer>> ret = new ArrayList<>();
    static List<Integer> temp = new ArrayList<>();

    public static List<List<Integer>> combine(int[] nums, int target) {
        back(nums,target,0);
        return ret;
    }

    /**
     * startIndex:单一集合求组合，因为是在自己里面，要靠index来框子集
     * 不需要的情况是多个集合
     */
    public static void back(int[] nums, int targetSum, int startIndex) {
        int sum = temp.stream()
                .mapToInt(Integer::intValue)
                .sum();
        if (targetSum == sum) {
            ret.add(new ArrayList<>(temp));
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            int cur = nums[i];
            //已经>=targetSum，要过滤掉
            if (sum + cur > targetSum) {
                continue;
            }
            temp.add(cur);

            /**
             * 这里之所以是i，是因为元素可以重复，所以本次循环，跟下次待组合的元素是一样
             *
             */
            back(nums, targetSum, i);
            temp.remove(temp.size() - 1);
        }
    }

}
